package nowcoder.offer;

import java.util.HashSet;

/**
 * 链表中环的入口结点
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-29 10:41
 */
public class EntryNodeOfLoop {

    public ListNode solution(ListNode pHead){

        if (pHead == null) return null;

        /**
         * 快慢指针的思路
         */
        ListNode slow = pHead,quick = pHead.next;

        while (slow != quick && quick != null){
            slow = slow.next;
            if (quick.next != null)
                quick = quick.next.next;
            else
                return null;
        }
        if (quick != null){
            slow = pHead;
            HashSet<ListNode> set = new HashSet<>();
            while (!set.contains(slow)){
                set.add(slow);
                slow = slow.next;
            }
            return slow;
        }

        return null;
    }


    public static void main(String[] args) {
        ListNode root = new ListNode(1);
//        root.next = new ListNode(2);
        new EntryNodeOfLoop().solution(root);
    }
}
